#!/usr/bin/env python3
# -*- coding: utf-8 -*-

import re
import collections


# Token specification
NUM = r'(?P<NUM>\d+)'
PLUS = r'(?P<PLUS>\+)'
MINUS = r'(?P<MINUS>-)'
TIMES = r'(?P<TIMES>\*)'
DIVIDE = r'(?P<DIVIDE>/)'
LPAREN = r'(?P<LPAREN>\()'
RPAREN = r'(?P<RPAREN>\))'
WS = r'(?P<WS>\s+)'

master_pat = re.compile('|'.join([NUM, PLUS, MINUS, TIMES, DIVIDE, LPAREN, RPAREN, WS]))

# Tokenizer
Token = collections.namedtuple('Token', ['type', 'value'])


def generator_tokens(text):
    scanner = master_pat.finditer(text)
    for s in scanner:
        tok = Token(s.lastgroup, s.group())
        if tok.type != 'WS':
            yield tok


# Parser
class ExpressionEvaluator:
    """
    实现一个递归下降解析器。每一个方法实现一条语法规则。
    使用 ._accept() 方法来测试并接受即将产生的 token。
    使用 ._expect() 方法来匹配并丢弃即将接收的 token，如果不匹配则抛出异常。
    """
    def __init__(self):
        self.tokens = None
        self.tok = None         # Last symbol consumed
        self.nexttok = None     # Next symbol tokenized

    def parse(self, text):
        self.tokens = generator_tokens(text)
        self._advance()         # Load first lookahead token
        return self.expr()

    def _advance(self):
        """Advance one token ahead"""
        self.tok, self.nexttok = self.nexttok, next(self.tokens, None)

    def _accept(self, toktype):
        """Test and consume the next token if it matches toktype"""
        if self.nexttok and self.nexttok.type == toktype:
            self._advance()
            return True
        else:
            return False

    def _expect(self, toktype):
        """Consume next token if it matches toktype or raise SyntaxError"""
        if not self._accept(toktype):
            raise SyntaxError('Expected ' + toktype)

    # 语法规则如下
    def expr(self):
        """expression ::= term { ('+'|'-') term }*"""
        exprval = self.term()
        while self._accept('PLUS') or self._accept('MINUS'):
            op = self.tok.type
            right = self.term()
            if op == 'PLUS':
                exprval += right
            elif op == 'MINUS':
                exprval -= right
        return exprval

    def term(self):
        """term ::= factor { ('*'|'/') factor }*"""
        termval = self.factor()
        while self._accept('TIMES') or self._accept('DIVIDE'):
            op = self.tok.type
            right = self.factor()
            if op == 'TIMES':
                termval *= right
            elif op == 'DIVIDE':
                termval /= right
        return termval

    def factor(self):
        """factor ::= NUM | (expr)"""
        if self._accept('NUM'):
            return int(self.tok.value)
        elif self._accept('LPAREN'):
            expval = self.expr()
            self._expect('RPAREN')
            return expval
        else:
            raise SyntaxError('Expected NUMBER or LPAREN')


class ExpressionTreeBuilder(ExpressionEvaluator):
    def expr(self):
        """"expression ::= term { ('+'|'-') term }*"""
        exprval = self.term()
        while self._accept('PLUS') or self._accept('MINUS'):
            op = self.tok.type
            right = self.term()
            if op == 'PLUS':
                exprval = ('+', exprval, right)
            elif op == 'MINUS':
                exprval = ('-', exprval, right)
        return exprval

    def term(self):
        """term ::= factor { ('*'|'/') factor }*"""
        termval = self.factor()
        while self._accept('TIMES') or self._accept('DIVIDE'):
            op = self.tok.type
            right = self.factor()
            if op == 'TIMES':
                termval = ('*', termval, right)
            elif op == 'DIVIDE':
                termval = ('/', termval, right)
        return termval

    def factor(self):
        """factor ::= NUM | (expr)"""
        if self._accept('NUM'):
            return int(self.tok.value)
        elif self._accept('LPAREN'):
            expval = self.expr()
            self._expect('RPAREN')
            return expval
        else:
            raise SyntaxError('Expected NUMBER or LPAREN')


if __name__ == '__main__':
    text1 = '2+(3+4)/2 * 5'
    text2 = '2+(2+3*4)/2 - 5'
    e = ExpressionTreeBuilder()
    print(e.parse(text1))
    print(e.parse(text2))
